#include <iostream>
#include <vector>

using namespace std;

class Trie
{
private:
    struct Node
    {
        char c;
        bool isEnd;
        vector<Node *> childs;

        Node(char c, bool isEnd)
        {
            this->c = c;
            this->isEnd = isEnd;
            childs.resize(26);
        }
    };

    Node root;

public:
    Trie() : root(' ', false)
    {
    }

    void insert(string word)
    {
        int ids = word[0] - 'a';
        auto cur = root.childs[ids];
        if (cur == nullptr)
        {
            cur = new Node(ids, false);
            root.childs[ids] = cur;
        }
        for (auto it = word.begin() + 1; it != word.end(); it++)
        {
            ids = *it - 'a';
            if (cur->childs[ids] == nullptr)
            {
                cur->childs[ids] = new Node(ids, false);
            }
            cur = cur->childs[ids];
        }
        cur->isEnd = true;
    }

    bool search(string word)
    {
        int ids = word[0] - 'a';
        auto cur = root.childs[ids];
        if (cur == nullptr)
        {
            return false;
        }
        for (auto it = word.begin() + 1; it != word.end(); it++)
        {
            ids = *it - 'a';
            if (cur->childs[ids] == nullptr)
            {
                return false;
            }
            cur = cur->childs[ids];
        }
        return cur->isEnd;
    }

    bool startsWith(string prefix)
    {
        int ids = prefix[0] - 'a';
        auto cur = root.childs[ids];
        if (cur == nullptr)
        {
            return false;
        }
        for (auto it = prefix.begin() + 1; it != prefix.end(); it++)
        {
            ids = *it - 'a';
            if (cur->childs[ids] == nullptr)
            {
                return false;
            }
            cur = cur->childs[ids];
        }
        return true;
    }
};

int main()
{
    cout << "Code208" << endl;
    cout << boolalpha;
    Trie trie = Trie();
    trie.insert("apple");
    cout << trie.search("apple") << endl;   // 返回 True
    cout << trie.search("app") << endl;     // 返回 False
    cout << trie.startsWith("app") << endl; // 返回 True
    trie.insert("app");
    cout << trie.search("app") << endl;    // 返回 True
    cout << trie.startsWith("appler") << endl; // 返回 False
    return 0;
}

/*
class Trie
{
private:
    struct Node
    {
        char c;
        bool isEnd;
        vector<Node> childs;

        Node(char c, bool isEnd)
        {
            this->c = c;
            this->isEnd = isEnd;
        }
    };

    Node root;

public:
    Trie() : root(' ', false)
    {
    }

    void insert(string word)
    {
        auto cur = find_if(root.childs.begin(), root.childs.end(), [word](Node n)
                           { return n.c == word[0]; });
        if (cur == root.childs.end())
        {
            root.childs.push_back(Node(word[0], false));
            cur = root.childs.end() - 1;
        }
        for (auto it = word.begin() + 1; it != word.end(); it++)
        {
            auto cr = find_if(cur->childs.begin(), cur->childs.end(), [it](Node n)
                              { return n.c == *it; });
            if (cr == cur->childs.end())
            {
                cur->childs.push_back(Node(*it, false));
                cr = cur->childs.end() - 1;
            }
            cur = cr;
        }
        cur->isEnd = true;
    }

    bool search(string word)
    {
        auto cur = find_if(root.childs.begin(), root.childs.end(), [word](Node n)
                           { return n.c == word[0]; });
        if (cur == root.childs.end())
        {
            return false;
        }
        for (auto it = word.begin() + 1; it != word.end(); it++)
        {
            auto cr = find_if(cur->childs.begin(), cur->childs.end(), [it](Node n)
                              { return n.c == *it; });
            if (cr == cur->childs.end())
            {
                return false;
            }
            cur = cr;
        }
        return cur->isEnd;
    }

    bool startsWith(string prefix)
    {
        auto cur = find_if(root.childs.begin(), root.childs.end(), [prefix](Node n)
                           { return n.c == prefix[0]; });
        if (cur == root.childs.end())
        {
            return false;
        }
        for (auto it = prefix.begin() + 1; it != prefix.end(); it++)
        {
            auto cr = find_if(cur->childs.begin(), cur->childs.end(), [it](Node n)
                              { return n.c == *it; });
            if (cr == cur->childs.end())
            {
                return false;
            }
            cur = cr;
        }
        return true;
    }
};
*/